#-*- encoding=utf-8 -*-

import copy
from collections import deque

class SolutionSearcher:
	# start_state -- 开始状态
	# end_state -- 结束状态
	# next_state -- 状态变迁函数 f: (state, position) ==> (state, position)
	# next_position -- 确定下一次探索方向 f: (state, position) => position
	# condition -- 状态约束条件 f: state ==> Ture/False
	# solve -- 根据开始状态/结束状态/状态变迁函数/状态约束条件，返回根据深度优先搜索算法求解的状态变迁路径

	def next_state(self, state, position):
		# TO BE OVERRIDE BY CHILD CLASS
		pass

	def next_position(self, state, position):
		# TO BE OVERRIDE BY CHILD CLASS
		pass

	def constraint(self, state):
		# TO BE OVERRIDE BY CHILD CLASS
		pass

	def solve(self, start_state, end_state):
		# 记录访问过的状态，在状态解空间中搜索目标状态时不允许访问重复状态（去除循环）
		visited_states = []
		# 待访问状态列表，后进先出队列（堆栈）实现深度优先搜索算法，其元素为state，当栈顶为目标状态时，栈顶到栈底就是反向搜索路径
		visiting_states = deque()
		# 把开始状态加入待访问状态队列
		visiting_states.append((start_state, None))
		# 加入到已访问队列
		visited_states.append(start_state)
		# 结束搜索标志
		solved = False
		# 搜索结果
		solution = []

		try_times = 0
		direction = 0
		state = start_state
		position = None
		while len(visiting_states) > 0:
			try_times += 1
			if state == end_state:
				break
			else:
				if direction == 0:
					s_next, p_next = self.next_state(state, position)
				else:
					position = self.next_position(state, position)
					if position is None:
						s_next, p_next = None, None
					else:
						s_next, p_next = self.next_state(state, position)

				if s_next is None:
					if p_next is None:
						(state, position) = visiting_states.pop()
					direction = 1
				elif self.constraint(s_next) and (s_next not in visited_states):
					visiting_states.append((s_next, p_next))
					visited_states.append(s_next)
					state, position = s_next, p_next
					direction = 0
				else:
					#继续探索(state, position)的下一个方向
					direction = 1
		print("try_times={}".format(try_times))
		for s, p in visiting_states:
			solution.append(s)
		return solution

	def print_solution(self, solution):
		if len(solution) > 0:
			print("find a solution with {} steps: ".format(len(solution)), end='')
			for s in solution:
				print(" =>", s, end='')
			print()
		else:
			print("no solution found!!!")

class FarmerIssue(SolutionSearcher):

	def constraint(self, state):
		#农夫不在时，狼会吃羊，羊会吃白菜
		fake_states = [['F','w','s','C'],['F','w','s','c'],['F','W','s','c'],['f','W','S','C'],['f','W','S','c'],['f','w','S','C']]
		return not(state in fake_states)

	def next_position(self, state, position):
		if position == None:
			position = 0

		if position + 1 >= len(state):
			return None
		else:
			return position + 1

	def next_state(self, state, position):
		#农夫一次只能带走一样东西过河
		if position == None:
			position = 0

		s = state[position]
		r = copy.deepcopy(state)
		for i in range(len(r)):
			if s == r[i]:
				#农夫不带任何东西过河
				if s == 'F':
					r[i] = 'f'
				elif s == 'f':
					r[i] = 'F'
				#农夫带狼过河
				elif s == 'W':
					r[i] = 'w'
				elif s == 'w':
					r[i] = 'W'
				#农夫带羊过河
				elif s == 'S':
					r[i] = 's'
				elif s == 's':
					r[i] = 'S'
				#农夫带白菜过河
				elif s == 'C':
					r[i] = 'c'
				elif s == 'c':
					r[i] = 'C'
			else:
				#农夫带东西过河时，自己也要过河
				if r[i] == 'F':
					r[i] = 'f'
				elif r[i] == 'f':
					r[i] = 'F'
		return r, 0

def solve_farmer_issue():
	#FWSC的顺序固定，大小写组合变化
	start_state = ['F', 'W', 'S', 'C'] 		#X--表示x在左岸，x--表示x在右岸, x的取值集合为(f,w,s,c)
	end_state = ['f', 'w', 's', 'c'] 		#f--代表farmer，w代表wolf，s代表sheep，c代表cabbage
	farmer_issue = FarmerIssue()
	solution = farmer_issue.solve(start_state, end_state)
	farmer_issue.print_solution(solution)

class HanoIssue(SolutionSearcher):

	def next_position(self, state, position):
		if position == None:
			(source, dest) = (0, 1)
		else:
			(source, dest) = position

		dest = dest + 1
		if dest >= 3:
			dest = 0
			source = source + 1
			if source >= 3:
				return None
			elif source == dest:
				return self.next_position(state, (source, dest))
		return source, dest

	def next_state(self, state, position):
		if position == None:
			(source, dest) = (0, 1)
		else:
			(source, dest) = position

		if len(state[source]) > 0:
			next_state = copy.deepcopy(state)
			next_state[dest].append(next_state[source].pop())
			return next_state, (0, 1)
		else:
			return None, position

	def is_sorted(self, array):
		i = 0
		n = len(array) - 1
		while i < n:
			if array[i] < array[i+1]:
				return False
			i = i + 1
		return True

	def constraint(self, state):
		for array in state:
			if not self.is_sorted(array):
				return False
		return True

def solve_hano_issue():
	start_state = [[8, 7, 6, 5, 4, 3, 2, 1], [], []]
	end_state = [[], [], [8, 7, 6, 5, 4, 3, 2, 1]]
	hano_issue = HanoIssue()
	solution = hano_issue.solve(start_state, end_state)
	hano_issue.print_solution(solution)

if __name__ == '__main__':
	solve_farmer_issue()
	solve_hano_issue()